Error diffusion is an idea generally credited to Floyd and Steinberg (See “An adaptive algorithm for spatial greyscale,” R. W. Floyd and L. Steinberg, Proceedings of the Society for Information Display, vol. 17, no. 2, pp. 75-77, 1976) and dates back to 1976, though it is equivalently a two-dimensional implementation of sigma-delta modulation, which as a tool for one-dimensional A/D converters dates at least to 1963 (see “A unity bit coding method by negative feedback,” H. Inose and Y. Yasuda, Proceedings of the IEEE, vol. 51, pp. 1524-1535, November 1963). As described therein, the basic error diffusion process is to raster scan the pixels, and for each pixel quantize it to black or white, then pass the error to neighboring pixels. However, the process is done serially, and for each pixel, the error between the original pixel and the quantized version is calculated and spatially filtered to pixels that have yet to be quantized. Thus pixels that are quantized are not the original pixels from the image, but the original pixels plus the error they have inherited from pixels previously quantized. FIG. 8 is a flow diagram showing a visual representation of the error diffusion process. Note that error diffusion is also equivalent to DPCM Differential Pulse Coded Modulation.
Error diffusion performs fairly well and is used often in practice. It is particularly good at accentuating edges in an image. Possibly the worst side effect is the graininess of a resulting image. In most applications, error diffusion quantizes between white and black, but error diffusion allows for a more general quantization. For instance, vector error diffusion of color images quantizes each incoming pixel to the closest of a small number of colors in a preset palette, where each color is defined by a three-dimensional vector.
Researchers have manipulated many factors in error diffusion, including the filter taps, the raster scan order, spatially-varying filters, adaptive filters approaches mixed with clustered dot dither, dot gain compensation, etc.
Halftoning takes a continuous image with many colors and creates an image that looks like the original but uses only two or a few colors. Halftoning is often implemented using the error diffusion algorithm, which is performed sequentially on pixels. To date, error diffusion is an algorithm performed on pixels, in the pixel domain.
Two papers, “Adaptive Error Diffusion for Multiresolution Rendering,” P. W. Wong. Society for Information Display Digest, 1994, and “Embedded Multilevel Error Diffusion,” J. R. Goldschneider, E. Riskin, P. W. Wong. IEEE Transactions on Image Processing, vol. 6, no. 7, July 1997, investigate the problem of designing an error diffused image that can be well rendered at many different resolutions. However, all of the operations therein are done in the pixel domain.
Other sources, including “Wavelet methods for compression, rendering, and descreening in digital halftoning,” N. A. Breaux and C. H. Chu. SPIE Conference Proceedings, vol. 3078, 1997, and “Multiresolution error-convergence halftone algorithm,” E. Peli. Journal of the Optical Society of America A, vol. 8, no. 4, April 1991, attempt to match the energy of each level in the halftone to the energy in that level of the multiresolutional original image. The goal of these sources is apparently to yield a halftone that is designed for progressive display at increasing resolution. These halftoning techniques do not use error diffusion.
One conference paper, “A Recursive Multiscale Error-Diffusion Technique for Digital Halftoning,” I. Katsavoundidis and C. C. Kuo, SPIE Conference Proceedings vol. 2094, 1993, also proposes the goal of multi-level mean-matching. This paper describes pixels being quantized, but in a random scan order. Error is diffused symmetrically about a quantized pixel, as opposed to the normal forward-only error propagation approach. However, because some neighboring pixels may already be quantized, the error that would have been passed to them is summed into a “global error” for that local region. These “global errors” are passed to neighboring regions using the same spatial error filter. The paper proposes the idea of passing some error from different regions within a scale. Again, however, it is the pixels themselves which are quantized.
The same authors refined their ideas and presented a modified algorithm in “A multiscale error diffusion technique for digital halftoning,” I. Katsavoundidis and C. C. Kuo, IEEE Transactions on Image Processing, vol. 6, no. 3, March 1997. That algorithm employs a nonlinear but non-random scanning order of the pixels, but still quantizes the pixels themselves, and still uses a non-causal filter (which is made possible due to the nonlinear scan order). The multiresolutional framework only affects the scan order of the pixels.
In “Neural Network Adaptive Digital Image Screen Halftoning (DISH) based on Wavelet Transform Preprocessing,” H. Szu, Y. Zhang, M. Sun, and C. C. Li, SPIE Conference Proceedings, vol. 2242, 1994, an adaptive screen for dithering was proposed in which the information about how to adapt the screen is pulled from the wavelet transform representation.
Speed of copying, printing, and processing are especially important to business customers. More image processing is moving to wavelet, or multiresolutional domains. Yet the image has traditionally had to be converted back to the pixel domain to do the error diffusion. Speed could be increased if this conversion could be avoided.